package checkers_seperate_classes;

import genericTree.GenericTree;
import genericTree.GenericTreeNode;
import genericTree.GenericTreeTraversalOrderEnum;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

import checkers_seperate_classes.CheckersData.SquareContent;

public class MoveAheadTree {
	private GenericTree<MoveNode> moveTree;
	private int targetMoveNumber;

	public void incrementNGeneration(int increment) {
		targetMoveNumber+=increment;
	}

	public MoveAheadTree() {
		targetMoveNumber = 0;
		MoveNode rootNode = new MoveNode(0);
		GenericTreeNode<MoveNode> aRoot = new GenericTreeNode<MoveNode>(rootNode);

		moveTree = new GenericTree<MoveNode>();
		moveTree.setRoot(aRoot);
	}

	public GenericTree<MoveNode> getMoveTree() {
		return moveTree;
	}

	public void expandGenerationsFromNodeBreadthFirst(int nGenerations, GenericTreeNode<MoveNode> startNode) {
		final boolean debug = false;

		if (debug) {
			System.out.println("Adding moves to the move tree");
			System.out.println(getMoveTree().toStringWithDepth());
		}
		incrementNGeneration(nGenerations);
		buildGenerationsHelper(startNode,1, BuildType.BreadthFirst);
	}

	enum BuildType {DepthFirst, BreadthFirst};

	void buildGenerationsHelper(GenericTreeNode<MoveNode> parentNode, int debugLevel, BuildType buildType) {

		/**
		 * Create the initial board based on parent moves
		 * Note, the moves are in reverse order
		 */
		Deque<CheckersMove> moves = new  LinkedList<CheckersMove>();

		GenericTreeNode<MoveNode> tempNode = parentNode;
		while(tempNode != null) {
			List<CheckersMove> nMoves = tempNode.getData().getMove();
			if (nMoves==null) {
				break;
			}
			for (final CheckersMove aMove : new ListReverser<CheckersMove>(nMoves)) {
				moves.addLast(aMove);
			}
			tempNode = tempNode.getParent();
		}
		if (debugLevel>1){
			System.out.println("\nThere are "+moves.size()+" initial moves:");
		}

		// Create the initial board based on move history
		Board initialBoard = new Board();
		while (! moves.isEmpty()) {
			CheckersMove nextMove = moves.removeLast();
			if (debugLevel>1){
				System.out.println("  "+CheckersData.toName(initialBoard.getNextPlayer())+" "+nextMove);
			}
			initialBoard.doMakeMove(nextMove, false);
		}
		// Get the list of possible moves to add as children
		final SquareContent nextPlayer = initialBoard.getNextPlayer();
		CheckersMove[] possibleMoves = initialBoard.board.getLegalMoves(nextPlayer);

		// Is the game over
		if (possibleMoves == null) {
			if (debugLevel>1) {
				if (nextPlayer == SquareContent.RED) {
					System.out.println("Black wins");
				} else {
					System.out.println("Red wins");
				}
				System.out.println(initialBoard);
			}
			return;
		}


		if (debugLevel>1){
			System.out.println("Initial board\n"+initialBoard);
			System.out.println("Adding "+possibleMoves.length+" moves:");
		}

		// To help with debuging, make a map between suspect moves and error message
		final HashMap<CheckersMove,String> errorList = new HashMap<>();

		// Make children using the possible moves
		boolean errorFlag = false;
		String errMsg = "null";
		if (debugLevel>1){
			System.out.println("Initial board is"+initialBoard.toString());
		}
		for (CheckersMove move:possibleMoves) {
			if (errorList.containsKey(move)) {
				errMsg = String.format("On move %s, error is: %s", move,errorList.get(move));
				System.out.println(errMsg);
				errorFlag = true;
			}
			// System.out.println("Making move "+move);
			// Make the move
			Board board = new Board(initialBoard);
			try {
				board.doMakeMove(move,false);
			} catch (NullPointerException e) {
				e.printStackTrace(System.out);
				NullPointerException e2 = new NullPointerException("Made "+move.toString()+" on board"+board.toString());
				e2.printStackTrace(System.out);
				throw e2;
			}

			// Add the move to the tree
			final double score = board.calculateScore();
			final int moveNumber = board.getMoveNumber();
			if (!(moveNumber<targetMoveNumber)) {
				continue;
			}
			MoveNode child = new MoveNode(move, score, nextPlayer, moveNumber);
			GenericTreeNode<MoveNode> childNode = new GenericTreeNode<MoveNode>(child);
			parentNode.addChild(childNode);
			if (debugLevel>2) {
				System.out.println("Board after move\n"+board);
			}
			if (buildType == BuildType.DepthFirst) {
				if (childNode.getData().getMoveNumber()<targetMoveNumber) {
					// System.out.println("move number "+moveNumber+" is less than "+targetMoveNumber);
					if (debugLevel>1){
						System.out.println("Generating children for node\n"+childNode);
					}
					buildGenerationsHelper(childNode, debugLevel, buildType);
				}
			}
			if (errorFlag) {
				throw new IllegalStateException(errMsg);
			}
		}
		if (buildType == BuildType.BreadthFirst) {
			for (GenericTreeNode<MoveNode> childNode:parentNode.getChildren()) {
				if (childNode.getData().getMoveNumber()<targetMoveNumber) {
					// System.out.println("move number "+moveNumber+" is less than "+targetMoveNumber);
					if (debugLevel>1){
						System.out.println("Generating children for node\n"+childNode);
					}
					buildGenerationsHelper(childNode, debugLevel, buildType);
				}
			}
		}
	}

	public String toString() {
		StringBuffer sb = new StringBuffer();
		sb.append("Target move number is "+this.targetMoveNumber);
		sb.append('\n');
		boolean oldWay = false;
		if (oldWay) {
			sb.append(this.moveTree.toStringWithDepth());
		} else {
			for (int iorder=1; iorder<=2; iorder++) {
				GenericTreeTraversalOrderEnum traversalOrder;
				if (iorder==1) {
					traversalOrder = GenericTreeTraversalOrderEnum.POST_ORDER;
				} else {
					traversalOrder = GenericTreeTraversalOrderEnum.PRE_ORDER;
				}
				sb.append("PRINT IN "+traversalOrder);
				sb.append('\n');
				List<GenericTreeNode<MoveNode>> nodeList = this.moveTree.build(traversalOrder );
				for (GenericTreeNode<MoveNode> entry:nodeList) {
					Integer depth = entry.getDepth();
					for (int indent=0; indent<depth; indent++) {
						sb.append("  ");
					}
					sb.append(entry.getData().toString());
					sb.append('\n');
				}
			}
		}

		return sb.toString();
	}

	public static void main(String[] args) throws FileNotFoundException {
		final boolean writeSysOutToFile = true;
		if (writeSysOutToFile) {
			File file  = new File("branches/src/checkers_seperate_classes/moveAhead.log");
			System.out.println("Writing output to "+file.getAbsolutePath());
			PrintStream printStream = new PrintStream(new FileOutputStream(file));
			System.setOut(printStream);
		}
		System.out.println("Generating next set of moves");
		MoveAheadTree mat = new MoveAheadTree();
	
		int iMove=0;
		
		GenericTreeNode<MoveNode> currentNode = mat.getMoveTree().getRoot();
		while (true) {
			iMove++;
			System.out.println("Start of move "+iMove);
			mat.expandGenerationsFromNodeBreadthFirst(3,currentNode);
//			System.out.println("Move tree:\n"+mat.toString());
			GenericTreeNode<MoveNode> nodeMoved = mat.getBestMove(currentNode,CheckersData.SquareContent.RED,1);
			Board board= new Board();
			CheckersMove move = nodeMoved.getData().getMove().get(0);
			board.doMakeMove(move, false);
			System.out.println("Move "+iMove+" red "+move+board.toString());
			nodeMoved = mat.getBestMove(nodeMoved, CheckersData.SquareContent.BLACK,1);
			move = nodeMoved.getData().getMove().get(0);
			board.doMakeMove(move, false);
			System.out.println("Move "+iMove+" black "+move+board.toString());
			currentNode = nodeMoved;
			System.out.println("End of move "+iMove);
		}
	}

	public GenericTreeNode<MoveNode> getBestMove(GenericTreeNode<MoveNode> currentNode, SquareContent aPlayer, int iMove) {
		rankTree();
		final SquareContent thisPlayer = aPlayer.toLower();
		List<GenericTreeNode<MoveNode>> moves = new ArrayList<>();
		getMovesHelper(currentNode, thisPlayer, iMove, moves);
		if (moves.isEmpty()) {
			throw new IllegalStateException("moves should not be empty");
		}
		GenericTreeNode<MoveNode> bestMove = moves.get(0);
		double bestScore = bestMove.getData().getScore();
		if (bestMove.hasChildren()) {
			double bestWinRatio = bestMove.getData().getNRedWins() 
					/ ((double)(bestMove.getData().getNChildren()));
			if (thisPlayer == SquareContent.BLACK) {
				bestWinRatio = 1.0 - bestWinRatio;
			}
			for (int i=1; i<moves.size(); i++) {
				double winRatio = moves.get(i).getData().getNRedWins() 
						/ ((double)(moves.get(i).getData().getNChildren()));
				if (thisPlayer == SquareContent.BLACK) {
					winRatio = 1.0 - winRatio;
				}
				if (winRatio > bestWinRatio) {
					bestWinRatio = winRatio;
					bestMove = moves.get(i);
				}
			}

		} else {
			for (int i=1; i<moves.size(); i++) {
				if (bestScore > moves.get(i).getData().getScore()) {
					bestMove = moves.get(i);
					bestScore = bestMove.getData().getScore();
				}
			}
		}
		return bestMove;
	}
	private void getMovesHelper(GenericTreeNode<MoveNode> node, 
			SquareContent thisPlayer, int iMove, List<GenericTreeNode<MoveNode>> moves) {
		List<GenericTreeNode<MoveNode>> liveChildren = new ArrayList<>();
		//		System.out.println("Looking for move "+iMove+" on player "+thisPlayer);
		//		int iChild=0;
		for (GenericTreeNode<MoveNode> child: node.getChildren()) {
			//			iChild++;
			final int moveNumber = child.getData().getMoveNumber();
			final SquareContent player = child.getData().getPlayer().toLower();
			//			System.out.println("Child "+iChild+" of "+node.getNumberOfChildren()+" has move "+moveNumber+" on player "+player);
			final boolean isNotEnoughMoves = moveNumber<iMove;
			final boolean hasEnoughMovesButWrongPlayer = moveNumber == iMove && !thisPlayer.equals(player); 
			final boolean hasEnoughMovesRightPlayer = moveNumber == iMove && thisPlayer.equals(player); 
			if (isNotEnoughMoves || hasEnoughMovesButWrongPlayer) {
				liveChildren.add(child);
			} else if (hasEnoughMovesRightPlayer) {
				moves.add(child);
			}
		}
		for (GenericTreeNode<MoveNode> child:liveChildren) {
			getMovesHelper(child, thisPlayer, iMove, moves);
		}
	}


	public void printNnodesWithoutChildren() {
		List<GenericTreeNode<MoveNode>> nodesWithoutChildren = getMoveTree().getNodesWithoutChildren();
		int nBlack, nRed;
		nBlack = nRed = 0;
		for (GenericTreeNode<MoveNode> entry:nodesWithoutChildren) {
			SquareContent player = entry.getData().getPlayer();
			switch(player) {
			case BLACK:
				nBlack++;
				break;
			case RED:
				nRed++;
				break;
			default:
				throw new IllegalStateException("no option for "+player);
			}			
		}
		System.out.println("After "+getNMoves()+" there are "+nodesWithoutChildren.size()+" children, "
				+nRed+" red, "+nBlack+" black");
	}

	private int getNMoves() {
		return this.targetMoveNumber;
	}

	/**
	 * Rank the tree so that each move knows how many children have winning 
	 * moves for red and losing moves for red
	 */
	public void rankTree() {
		GenericTreeNode<MoveNode> aNode = this.moveTree.getRoot();

		rankChildren(aNode);
	}

	private void rankChildren(GenericTreeNode<MoveNode> aNode) {
		for (GenericTreeNode<MoveNode> aChild:aNode.getChildren()) {
			GenericTreeNode<MoveNode> parent = aChild.getParent();
			MoveNode parentData = parent.getData();
			parentData.incrementNChildren();
			if(aChild.hasChildren()) {
				rankChildren(aChild);
				MoveNode childData = aChild.getData();
				final int nChildren = aNode.getNumberOfChildren();
				final int nChildrenRedWinning = childData.getNRedWins();
				final double ratioRedWinning = ((double)nChildrenRedWinning) / nChildren;
				if (ratioRedWinning > 0.5) {
					parentData.incrementChildrenWithRedWins();
				} 
			} else {
				MoveNode childData = aChild.getData();
				final double childScore = childData.getScore();
				final SquareContent childPlayer = childData.getPlayer();
				if (childScore > 0 & childPlayer == SquareContent.RED) {
					parentData.incrementChildrenWithRedWins();
				} 
			}			
		}
	}
}